package writtenexamination.weimeng;

import algorithm.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author cyt
 * @create 2020-10-11 下午 5:17
 */
public class Td {


    private static Map<Integer, Integer> indexForInOrders = new HashMap<>();

    public static void main(String[] args) {

    }

    static long[] ans;
    static int k = 0;

    public long[] buildPostOrder(long[] preorderData, long[] inorderData) {
        for (int i = 0; i < inorderData.length; i++) {
            indexForInOrders.put((int) inorderData[i], i);
        }
        TreeNode dfs = dfs(preorderData, 0, preorderData.length - 1, 0);
        postVis(dfs);
        return ans;
    }

    void postVis(TreeNode node) {
        /**
         *        1
         *   2         3
         *     4     5  8
         *  7       6
         *
         */
        if (node == null) {
            return;
        }
        postVis(node.left);
        postVis(node.right);
        ans[k++] = node.val;
        System.out.println(node.val);
    }

    public TreeNode dfs(long[] pre, int preL, int preR, int inL) {
        // 结束递归
        if (preL > preR)
            return null;
        // 根节点
        TreeNode root = new TreeNode((int) pre[preL]);
        // 左子树
        // 当前根节点 在中序遍历中的位置
        int inIndex = indexForInOrders.get(root.val);
        int left = inIndex - inL;
        root.left = dfs(pre, preL + 1, preL + left, inL);
        // 右子树
        root.right = dfs(pre, preL + left + 1, preR, inL + 1 + left);
        return root;
    }
}
